package cn.edu.jxau.test;

import java.io.IOException;
import java.util.Arrays;

public class Main {

    public static void main(String[] args) throws IOException {

        char[] arr = { 'E', 'A', 'S', 'Y', 'Q', 'U', 'E', 'S', 'T', 'I', 'O', 'N' };
        System.out.println(Arrays.toString(arr));
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void sort(char[] charArr) {

        char[] aux = new char[charArr.length]; // 辅助空间
        sort(charArr, aux, 0, charArr.length - 1);
    }

    private static void sort(char[] charArr, char[] aux, int low, int high) {

        if (high <= low) {
            return;
        }
        int mid = low + (high - low) / 2;
        sort(charArr, aux, low, mid);
        sort(charArr, aux, mid + 1, high);
        merge(charArr, aux, low, high);
    }

    private static void merge(char[] charArr, char[] aux, int low, int high) {

        int mid = low + (high - low) / 2;
        int i = low;
        int j = high;
        for (int k = low; k <= mid; k++) { // 左半边正序
            aux[k] = charArr[k];
        }
        for (int k = mid + 1; k <= high; k++) { // 右半边逆序
            aux[k] = charArr[high - k + mid + 1];
        }
        for (int k = low; k <= high; k++) { // 从两端归并，减少逻辑判断
            if (aux[i] < aux[j]) {
                charArr[k] = aux[i++];
            } else {
                charArr[k] = aux[j--];
            }
        }
    }
}
